// m

// 给定一个链表的头节点head
// 要求判断链表中是否有环，如果有环则返回入环的第一个节点，无环则返回null


// 思路：快慢指针（Floyd判圈算法）
// 1.利用两个指针，满指针slow每次前进一步，快指针fast每次前进两步（两步或者多步是等效的）
// 2. 如果两个指针在链表头结点以外的某一节点相遇，那么说明链表有环
// 3. 否则，如果快指针到达了某个没有后继指针的节点时，那么说明没环
// 4. 如果有环，则再定义一个指针ans，和慢指针一起每次移动一步，两个指针相遇的位置即为入口节点
const {ListNode, LinkedList} = require('../../1. 链表基础/1. 建立线性链表')
function detectCycle(head) {
    let fast = head
    let slow = head
    while (true) {
        if (!fast || !fast.next) {
            return null
        }
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) {
            break
        }
    }
    let ans = head
    while (ans !== slow) {
        ans = ans.next
        slow = slow.next
    }
    return ans
}

let node0 = new ListNode('abin')
let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node0.next = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

console.log(detectCycle(node0))

var detectCycle = function(head) {
    if(!head || !head.next) {
        return null
    }
    let slow = head
    let fast = head.next
    while(slow !== fast) {
        if(!fast || !fast.next) {
            return null
        }
        slow = slow.next
        fast = fast.next.next
    }
    slow = head
    while(slow !== fast) {
        slow = slow.next
        fast = fast.next
    }
    return slow

};

// console.log(detectCycle(node0))


function hasCycle2(head) {
    if (!head || !head.next) {
        return false
    }
    let slow = head
    let fast = head.next
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return false
        }
        slow = slow.next
        fast = fast.next.next
    }
    return true
}
console.log(hasCycle2(node0))

